#include "CVirtualTextureManager.h"


	CVirtualTextureManager::CVirtualTextureManager(): _uMaxBlockDim(0)
	{
	}


	CVirtualTextureManager::~CVirtualTextureManager()
	{
		Destroy();
	}


	bool CVirtualTextureManager::Create(const TDescriptor &sDescr)
	{
		CHECK_ARGUMENT( !sDescr.aTexInfo.Empty()	 &&
						IsPOT( sDescr.vDimension.x ) &&
						IsPOT( sDescr.vDimension.y ) &&
						IsPOT( sDescr.uBlockDim ) );

		Destroy();

		_vDimension 	 = uvec2( GetPOT( sDescr.vDimension.x ), GetPOT( sDescr.vDimension.y ) );
		_uMaxBlockDim	 = sDescr.uBlockDim;
		uint	u_layers = GetPOT( sDescr.vDimension.Max() ) - 2;

		_aTextures.Resize( sDescr.aTexInfo.Count(), false );
		_aLayers.Resize( u_layers >> 1, false );

		for (usize i = 0; i < sDescr.aTexInfo.Count(); ++i)
		{
			CHECK_RETURN( RESMAN()->Create( e_resource::TEXTURE_2D, _aTextures[i].pMain ) );
			CHECK_RETURN( RESMAN()->Create( e_resource::TEXTURE_2D, _aTextures[i].pReserve ) );

			CHECK_RETURN( _aTextures[i].pMain->CreateRT( uvec3(sDescr.vDimension, 0), sDescr.aTexInfo[i].eFormat,
											sDescr.aTexInfo[i].eSwizzle, sDescr.aTexInfo[i].eFlags ) );

			CHECK_RETURN( _aTextures[i].pReserve->CreateRT( uvec3(_uMaxBlockDim, _uMaxBlockDim, 0),
						sDescr.aTexInfo[i].eFormat, sDescr.aTexInfo[i].eSwizzle, sDescr.aTexInfo[i].eFlags ) );
		}


		for (usize i = 0; i < _aLayers.Count(); ++i)
		{
			_aLayers[i].uMinBlockPO2 = (i << 1) + 1;
		}

		const uint	u_dim	= 1 << ((u_layers & ~1) + 1);
		const uvec2	v_count	= sDescr.vDimension / u_dim;


		for (uint y = 0; y < v_count.y; ++y)
		for (uint x = 0; x < v_count.x; ++x)
		{
			TBlock	block;

			block.sUpLevel.x	 = u_dim * x;
			block.sUpLevel.y	 = u_dim * y;
			block.sUpLevel.layer = _aLayers.Count();
			block.sUpLevel.size	 = 0;

			_aLayers.Back().aBlocks.PushBack( block );
		}

		_sDefaultIndex.x	 = 0;
		_sDefaultIndex.y	 = 0;
		_sDefaultIndex.layer = 0;
		_sDefaultIndex.size	 = 0;

		return true;
	}


	void CVirtualTextureManager::Destroy()
	{
		_aLayers.Clear();
		_aTextures.Clear();
		_vDimension   = uvec2(0);
		_uMaxBlockDim = 0;

		_sDefaultIndex.x	 = 0;
		_sDefaultIndex.y	 = 0;
		_sDefaultIndex.layer = 0;
		_sDefaultIndex.size	 = 0;
	}

	
	template <uint X, uint Y>
	inline void CalcNewIndex(uint uLayer, const CVirtualTextureManager::index_t &sFrom,
							 uint uPos, CVirtualTextureManager::index_t &sIndex)
	{
		STATIC_ASSERT( (X <= 4 && X > 0) && (Y <= 4 && Y > 0), "" );

		const uint	layer = (uLayer<<1) + 1;

		sIndex.x	 = sFrom.x + ((uPos & 0x3) << layer );
		sIndex.y	 = sFrom.y + (((uPos >> 2) & 0x3) << layer );
		sIndex.layer = uint8( uLayer );
		sIndex.size  = (X-1) | ((Y-1)<<2);
	}

	
	template <uint MX, uint X, uint Y>
	struct TGetFreeIndex
	{
		template <uint iX>	static INLINE uint _GetXBits(uint bits)		{ return ((bits >> (iX)) & 1) | _GetXBits<iX-1>( bits ); }
		template <>			static INLINE uint _GetXBits<0>(uint bits)	{ return (bits & 1); }
		template <uint iY>	static INLINE uint _GetYBits(uint bits)		{ return _GetXBits<X-1>( bits ) | _GetYBits<iY-1>( bits >> MX ); }
		template <>			static INLINE uint _GetYBits<0>(uint bits)	{ return _GetXBits<X-1>( bits ); }

		template <uint iX>	static INLINE uint _GetXMask()				{ return (1 << (iX)) | _GetXMask<iX-1>(); }
		template <>			static INLINE uint _GetXMask<0>()			{ return 1; }
		template <uint iY>	static INLINE uint _GetYMask()				{ return _GetXMask<X-1>() | (_GetYMask<iY-1>() << MX); }
		template <>			static INLINE uint _GetYMask<0>()			{ return _GetXMask<X-1>(); }


		static INLINE uint GetBits(uint16 bits)							{ return _GetYBits<Y-1>( bits ); }
		static INLINE uint GetMask(uint i)								{ return _GetYMask<Y-1>() << i; }
	};

	
	inline uint GetFreeIndex(uint16 &bits)
	{
		for (uint i = 0; i < sizeof(bits)<<3; ++i)
		{
			if ( ((bits >> i) & 1) == 0 )
			{
				bits |= 1<<i;
				return i;
			}
		}

		return -1;
	}

	
	template <uint X, uint Y>
	inline uint GetFreeIndex(uint16 &bits)
	{
		STATIC_ASSERT( (X <= 4 && X > 0) && (Y <= 4 && Y > 0), "" );

		for (uint y = 0; y <= 4-Y; ++y)
		for (uint x = 0; x <= 4-X; ++x)
		{
			const uint	i = x | (y<<2);

			if ( TGetFreeIndex<4,X,Y>::GetBits( bits >> i ) == 0 )
			{
				bits |= TGetFreeIndex<4,X,Y>::GetMask( i );
				return i;
			}
		}

		return -1;
	}
	

	inline void ReleaseIndex(uint16 &bits, uint size, uint x, uint y)
	{
		switch ( size )
		{
			case (0 | (0<<2)) :		bits &= ~TGetFreeIndex< 4, 1, 1 >::GetMask( x | (y<<2) );	break;
			case (1 | (0<<2)) :		bits &= ~TGetFreeIndex< 4, 2, 1 >::GetMask( x | (y<<2) );	break;
			case (2 | (0<<2)) :		bits &= ~TGetFreeIndex< 4, 3, 1 >::GetMask( x | (y<<2) );	break;
			case (3 | (0<<2)) :		bits &= ~TGetFreeIndex< 4, 4, 1 >::GetMask( x | (y<<2) );	break;
			case (0 | (1<<2)) :		bits &= ~TGetFreeIndex< 4, 1, 2 >::GetMask( x | (y<<2) );	break;
			case (1 | (1<<2)) :		bits &= ~TGetFreeIndex< 4, 2, 2 >::GetMask( x | (y<<2) );	break;
			case (2 | (1<<2)) :		bits &= ~TGetFreeIndex< 4, 3, 2 >::GetMask( x | (y<<2) );	break;
			case (3 | (1<<2)) :		bits &= ~TGetFreeIndex< 4, 4, 2 >::GetMask( x | (y<<2) );	break;
			case (0 | (2<<2)) :		bits &= ~TGetFreeIndex< 4, 1, 3 >::GetMask( x | (y<<2) );	break;
			case (1 | (2<<2)) :		bits &= ~TGetFreeIndex< 4, 2, 3 >::GetMask( x | (y<<2) );	break;
			case (2 | (2<<2)) :		bits &= ~TGetFreeIndex< 4, 3, 3 >::GetMask( x | (y<<2) );	break;
			case (3 | (2<<2)) :		bits &= ~TGetFreeIndex< 4, 4, 3 >::GetMask( x | (y<<2) );	break;
			case (0 | (3<<2)) :		bits &= ~TGetFreeIndex< 4, 1, 4 >::GetMask( x | (y<<2) );	break;
			case (1 | (3<<2)) :		bits &= ~TGetFreeIndex< 4, 2, 4 >::GetMask( x | (y<<2) );	break;
			case (2 | (3<<2)) :		bits &= ~TGetFreeIndex< 4, 3, 4 >::GetMask( x | (y<<2) );	break;
			case (3 | (3<<2)) :		bits &= ~TGetFreeIndex< 4, 4, 4 >::GetMask( x | (y<<2) );	break;
		};
	}


	bool CVirtualTextureManager::_GetFreeTexture(const uvec2 &vDim, index_t &sIndex)
	{
		typedef uint (*PGetFreeIndexProc_t)(uint16 &);
		typedef void (*PCalcNewIndexProc_t)(uint, const index_t &, uint, index_t &);

		static PGetFreeIndexProc_t	s_aGetFreeIndexProcs[] = {
			& GetFreeIndex,			& GetFreeIndex<1,2>,	& GetFreeIndex<1,3>,	& GetFreeIndex<1,4>,
			& GetFreeIndex<2,1>,	& GetFreeIndex<2,2>,	& GetFreeIndex<2,3>,	& GetFreeIndex<2,4>,
			& GetFreeIndex<3,1>,	& GetFreeIndex<3,2>,	& GetFreeIndex<3,3>,	& GetFreeIndex<3,4>,
			& GetFreeIndex<4,1>,	& GetFreeIndex<4,2>,	& GetFreeIndex<4,3>,	& GetFreeIndex<4,4>
		};

		static PCalcNewIndexProc_t	s_aCalcNewIndexProcs[] = {
			& CalcNewIndex<1,1>,	& CalcNewIndex<1,2>,	& CalcNewIndex<1,3>,	& CalcNewIndex<1,4>,
			& CalcNewIndex<2,1>,	& CalcNewIndex<2,2>,	& CalcNewIndex<2,3>,	& CalcNewIndex<2,4>,
			& CalcNewIndex<3,1>,	& CalcNewIndex<3,2>,	& CalcNewIndex<3,3>,	& CalcNewIndex<3,4>,
			& CalcNewIndex<4,1>,	& CalcNewIndex<4,2>,	& CalcNewIndex<4,3>,	& CalcNewIndex<4,4>
		};

		ASSERT( vDim.Max() <= _MaxBlockSize() );

		const uint	layer	= _s_GetLayer( vDim.Max() );
		uvec2		size	= uvec2( GetPOT( vDim.x ), GetPOT( vDim.y ) ) - _aLayers[layer].uMinBlockPO2;
		uint		index	= 0;
		const uint	proc	= size.x + (size.y<<2);


		for (usize i = 0; i < _aLayers[layer].aBlocks.Count(); ++i)
		{
			TBlock &	block	= _aLayers[layer].aBlocks[i];
			
			if ( block.uBits == uint16(-1) )
				continue;

			const uint	pos		= s_aGetFreeIndexProcs[proc]( block.uBits );

			if ( pos == -1 )
				continue;

			s_aCalcNewIndexProcs[proc]( layer, block.sUpLevel, pos, sIndex );
			return true;
		}
		

		// find in up levels
		if ( !_AllocTexture( layer, index ) )
			return false;
		
		TBlock &	block	= _aLayers[layer].aBlocks[ index ];
		const uint	pos		= s_aGetFreeIndexProcs[proc]( block.uBits );
		ASSERT( pos != -1 );

		s_aCalcNewIndexProcs[proc]( layer, block.sUpLevel, pos, sIndex );
		return true;
	}


	bool CVirtualTextureManager::_AllocTexture(const uint uLayer, uint &uBlockIndex)
	{
		uint	layer		= uLayer+1;
		uint	block_idx	= -1;

		// find free block in up levels
		for (; layer < _aLayers.Count(); ++layer)
		{
			for (usize i = 0; i < _aLayers[layer].aBlocks.Count(); ++i)
			{
				TBlock &	block	= _aLayers[layer].aBlocks[i];
				
				if ( block.uBits == uint16(-1) )
					continue;

				const uint	pos		= GetFreeIndex( block.uBits );

				if ( pos == -1 )
					continue;

				TBlock		new_block;

				new_block.uBits = 0;

				CalcNewIndex<1,1>( layer, block.sUpLevel, pos, new_block.sUpLevel );
				
				--layer;

				block_idx = (uint)_aLayers[layer].aBlocks.Count();
				_aLayers[layer].aBlocks.PushBack( new_block );

				goto ExitCycle;
			}
		}

		WARNING( "no free memory in virtual texture" );
		return false;

	ExitCycle:

		// create blocks in down levels
		for (; layer > uLayer;)
		{
			TBlock		new_block;
			TBlock &	block	= _aLayers[layer].aBlocks[ block_idx ];
			const uint	pos		= GetFreeIndex( block.uBits );
			
			ASSERT( pos != -1 );
			
			new_block.uBits		= 0;
			CalcNewIndex<1,1>( layer, block.sUpLevel, pos, new_block.sUpLevel );

			--layer;

			block_idx = (uint)_aLayers[layer].aBlocks.Count();
			_aLayers[layer].aBlocks.PushBack( new_block );
		}

		ASSERT( layer == uLayer );

		uBlockIndex = block_idx;
		return true;
	}


	bool CVirtualTextureManager::AllocTexture(const uvec2 &vDim, urect &sTexCoord, index_t &sIndex)
	{
		const uvec2		v_dim = vDim + 2;

		CHECK_RETURN( _GetFreeTexture( v_dim, sIndex ) );
		
		sTexCoord = urect( sIndex.x, sIndex.y, v_dim.x, v_dim.y );
		return true;
	}


	bool CVirtualTextureManager::AddTexture(const TImage2D &sImage, const index_t &sIndex, uint uTexture)
	{
		CHECK_ARGUMENT( uTexture < _aTextures.Count() &&
						Any( sImage.vTexDim <= _s_GetSize( sIndex ) ) );

		CHECK_RETURN( _aTextures[uTexture].pMain->AddImage( sImage, uvec2( sIndex.x, sIndex.y ) ) );
		return true;
	}


	bool CVirtualTextureManager::AddTextureAsync(const TImage2D &sImage, const index_t &sIndex, uint uTexture)
	{
		CHECK_ARGUMENT( uTexture < _aTextures.Count() &&
						Any( sImage.vTexDim <= _s_GetSize( sIndex ) ) );

		CHECK_RETURN( _aTextures[uTexture].pReserve->AddImage( sImage, uvec2( sIndex.x, sIndex.y ) ) );
		
		// TODO: add copy operation
		return true;
	}


	bool CVirtualTextureManager::AddTexture(const array<TImage2D> &aImages, urect &sTexCoord, index_t &sIndex)
	{
		CHECK_ARGUMENT( aImages.Count() == _aTextures.Count() );

		//AUTO_SYNC( _sCSLockTex, TCriticalSection::TAutoLock );

		const uvec2		v_dim = aImages.Front().vTexDim + 2;

		CHECK_RETURN( _GetFreeTexture( v_dim, sIndex ) );

		sTexCoord = urect( sIndex.x, sIndex.y, sIndex.x + v_dim.x, sIndex.y + v_dim.y );

		for (usize i = 0; i < _aTextures.Count(); ++i)
		{
			CHECK_VALUE( All( aImages[i].vTexDim + 2 == v_dim ) );
			CHECK_RETURN( _aTextures[i].pMain->AddImage( aImages[i], uvec2( sIndex.x, sIndex.y ) ) );
		}

		return true;
	}


	bool CVirtualTextureManager::AddTextureAsync(const array<TImage2D> &aImages, urect &sTexCoord, index_t &sIndex)
	{
		CHECK_ARGUMENT( aImages.Count() == _aTextures.Count() );

		//AUTO_SYNC( _sCSLockTex, TCriticalSection::TAutoLock );

		const uvec2		v_dim = aImages.Front().vTexDim + 1;

		CHECK_RETURN( _GetFreeTexture( v_dim, sIndex ) );
		
		sTexCoord = urect( sIndex.x, sIndex.y, sIndex.x + v_dim.x, sIndex.y + v_dim.y );

		for (usize i = 0; i < _aTextures.Count(); ++i)
		{
			CHECK_VALUE( All( aImages[i].vTexDim + 1 == v_dim ) );
			CHECK_RETURN( _aTextures[i].pReserve->AddImage( aImages[i], uvec2(0) ) );
		}

		// TODO: add copy operation

		return true;
	}


	bool CVirtualTextureManager::FreeTexture(const index_t& sIndex)
	{
		//AUTO_SYNC( _sCSLockTex, TCriticalSection::TAutoLock );

		index_t				index;
		array< TBlock >	&	a_blocks = _aLayers[ sIndex.layer ].aBlocks;
		const uint			mask	 = 0x3 << ( (sIndex.layer << 1) + 1 );

		index.x = sIndex.x & ~mask;
		index.y = sIndex.y & ~mask;
		

		for (usize i = 0; i < a_blocks.Count(); ++i)
		{
			if ( _s_CmpIndex( a_blocks[i].sUpLevel, index ) )
			{
				ReleaseIndex( a_blocks[i].uBits, sIndex.size, sIndex.x & mask, sIndex.y & mask );

				if ( a_blocks[i].uBits == 0 && uint(sIndex.layer+1) < _aLayers.Count() )
				{
					CHECK_RETURN( FreeTexture( a_blocks[i].sUpLevel ) );
					a_blocks.FastErase( i );
				}
				return true;
			}
		}

		return false;
	}

	
	bool CVirtualTextureManager::Test()
	{
		TDescriptor		s_descr;

		s_descr.aTexInfo.PushBack( TDescriptor::TTexture( e_rt_format::RGBA8, e_tex_swizzle::AUTO,
									e_tex_flags::BILINEAR | e_tex_flags::REPEAT ) );
		s_descr.vDimension = uvec2( 1024 );

		bool	ret = true;
		index_t	index;

		ret &= Create( s_descr );
		ret &= _GetFreeTexture( uvec2(256), index );
		ret &= FreeTexture( index );

		ret &= _GetFreeTexture( uvec2(64), index );
		ret &= _GetFreeTexture( uvec2(256), index );
		ret &= _GetFreeTexture( uvec2(256), index );
		ret &= _GetFreeTexture( uvec2(64), index );
		ret &= _GetFreeTexture( uvec2(64), index );
		ret &= _GetFreeTexture( uvec2(16), index );
		ret &= _GetFreeTexture( uvec2(16), index );
		ret &= _GetFreeTexture( uvec2(16), index );
		ret &= _GetFreeTexture( uvec2(16), index );
		ret &= _GetFreeTexture( uvec2(16), index );
		ret &= _GetFreeTexture( uvec2(16), index );
		ret &= _GetFreeTexture( uvec2(16), index );
		ret &= _GetFreeTexture( uvec2(16), index );
		ret &= _GetFreeTexture( uvec2(16), index );
		ret &= _GetFreeTexture( uvec2(64), index );
		ret &= _GetFreeTexture( uvec2(64), index );
		ret &= _GetFreeTexture( uvec2(16), index );
		ret &= _GetFreeTexture( uvec2(16), index );
		ret &= _GetFreeTexture( uvec2(16), index );
		ret &= _GetFreeTexture( uvec2(16), index );
		ret &= _GetFreeTexture( uvec2(16), index );
		ret &= _GetFreeTexture( uvec2(16), index );
		ret &= _GetFreeTexture( uvec2(16), index );
		ret &= _GetFreeTexture( uvec2(16), index );
		ret &= _GetFreeTexture( uvec2(16), index );
		ret &= _GetFreeTexture( uvec2(64), index );
		ret &= _GetFreeTexture( uvec2(64), index );
		ret &= _GetFreeTexture( uvec2(16), index );
		ret &= _GetFreeTexture( uvec2(16), index );
		ret &= _GetFreeTexture( uvec2(16), index );
		ret &= _GetFreeTexture( uvec2(16), index );
		ret &= _GetFreeTexture( uvec2(16), index );
		ret &= _GetFreeTexture( uvec2(16), index );
		ret &= _GetFreeTexture( uvec2(16), index );
		ret &= _GetFreeTexture( uvec2(16), index );
		ret &= _GetFreeTexture( uvec2(16), index );
		ret &= FreeTexture( index );

		return ret;
	}
